\documentclass[11pt]{article}
%\documentclass{sig-alternate}
\usepackage{algorithm}
\usepackage{algorithmic}

\usepackage{subfigure}
\usepackage{epsfig,amsthm,amsmath,color, amsfonts}
\usepackage{epsfig,color}
\usepackage{framed}
%\usepackage{epsf}
%\usepackage{hyperref}
%\usepackage{fullpage}

%\setlength{\textheight}{9.4in} \setlength{\textwidth}{6.55in}
\setlength{\textheight}{9.2in} \setlength{\textwidth}{6.55in}
%\setlength{\topmargin}{0in}

\voffset=-0.9in \hoffset=-0.8in

\newtheorem{theorem}{Theorem}[section]
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{conjecture}[theorem]{Conjecture}
%\newtheorem{example}[theorem]{Example}
\newtheorem{remark}[theorem]{Remark}
\theoremstyle{definition}\newtheorem{example}[theorem]{Example}
\theoremstyle{definition}\newtheorem{definition}[theorem]{Definition}
\theoremstyle{observation}\newtheorem{observation}[theorem]{Observation}

\newcommand{\comment}[1]{}
\newcommand{\QED}{\mbox{}\hfill \rule{3pt}{8pt}\vspace{10pt}\par}
%\newcommand{\eqref}[1]{(\ref{#1})}
\newcommand{\theoremref}[1]{(\ref{#1})}
\newenvironment{proof1}{\noindent \mbox{}{\bf Proof:}}{\QED}
%\newenvironment{observation}{\mbox{}\\[-10pt]{\sc Observation.} }%
%{\mbox{}\\[5pt]}

\def\m{{\rm min}}
%\def\m{\bar{m}}
\def\eps{{\epsilon}}
\def\half{{1\over 2}}
\def\third{{1\over 3}}
\def\quarter{{1\over 4}}
\def\polylog{\operatorname{polylog}}
\newcommand{\ignore}[1]{}
\newcommand{\eat}[1]{}
\newcommand{\floor}[1]{\left\lfloor #1 \right\rfloor}
\newcommand{\ceil}[1]{\left\lceil #1 \right\rceil}

\newcommand{\algorithmsize}[0]{}

%---------------------
%  SPACE SAVERS
%---------------------

%\usepackage{times}
%\usepackage[small,compact]{titlesec}
%\usepackage[small,it]{caption}

%\newcommand{\squishlist}{
% \begin{list}{$\bullet$}
%  { \setlength{\itemsep}{0pt}
%     \setlength{\parsep}{3pt}
%     \setlength{\topsep}{3pt}
%     \setlength{\partopsep}{0pt}
%     \setlength{\leftmargin}{1.5em}
%     \setlength{\labelwidth}{1em}
%     \setlength{\labelsep}{0.5em} } }
%\newcommand{\squishend}{
%  \end{list}  }

\newcommand{\squishlist}{\begin{itemize}}
\newcommand{\squishend}{\end{itemize}}

%---------------------------------
% FOR MOVING PROOFS TO APPENDIX
%\usepackage{answers}
%%\usepackage[nosolutionfiles]{answers}
%\Newassociation{movedProof}{MovedProof}{movedProofs}
%\renewenvironment{MovedProof}[1]{\begin{proof}}{\end{proof}}

\def\e{{\rm E}}
\def\var{{\rm Var}}
\def\ent{{\rm Ent}}
\def\eps{{\epsilon}}
\def\lam{{\lambda}}
\def\bone{{\bf 1}}


\def\danupon#1{\marginpar{$\leftarrow$\fbox{D}}\footnote{$\Rightarrow$~{\sf #1 --Danupon}}}
%
%Second definitions. Use these to remove all comments.
%\def\danupon#1{}


\begin{document}


\title{Changes made in this revision}
\author{}
\date{}

\maketitle


We have made the following changes and clarifications to the definition
of the problem. First, we clarified that we assume the input
items to be indivisible. We also emphasized that in this paper we only
consider the case where these items are edges. Secondly, in response
to reviewer 2, we add a minor assumption that $n$ is known to the
algorithm before reading the stream. We also note that this
assumption could be slightly relaxed.

We also clarified the statement and proof of Lemma~5.2 as suggested
by the reviewers.

Besides fixing the typos suggested by the reviewers, we would like
to mention the following minor changes.

\paragraph{Reviewer 1:} The reviewer suggested
that we make it more formal that the model is about graph
properties. We have added a comment that in this paper we are only interested in the
case where input items are edges. However, we still
define the problem in a general way since there are other problems
where the input consists of other types of items (e.g., numbers).
%
We also clarified the example before the statement of Lemma~2.1.

%The reviewer commented:
%
%\begin{quote}... technically one should also observe that the simulating
%protocol, when it is not simulating the ``correct" best-order
%streaming algorithm $A$ the answer is still ``correct" in the sense
%that ...
%\end{quote}
%
%This is a nice observation but we did not add anything to the paper
%regarding this since we are not sure it will help in understanding
%the proof (and afraid that it may confuse the readers).


\paragraph{Reviewer 2:} The reviewer comment:

\begin{quote}
My understanding is that there are a handful of references relating
to the best-case partition (following up in KN97 there seems to be
only 1 or 2 mentioned), which is dwarfed by the huge literature on
worst case.  Probably the reason for this is that for the kind of
problems most commonly studied in communication complexity, such as
disjointness, pointer jumping etc., become trivially easy in the
best case partition.
\end{quote}

We added a comment that the early results in communication
complexity are actually in this model since it has applications in
VLSI design (see, e.g., KN97). (So, although the later results on
the worst-case model have dominated these early results, there are
 a few results on this best-case partition.) We also added a
few more references for completeness.


The reviewer commented:

\begin{quote}
P7 For the protocol, should there be a bound on the number of rounds
used in $\mathcal{P}$?
\end{quote}

Our response is that bounding the number of rounds would give
stronger lower bounds. But the results in our paper do not need such
a restriction so we did not add this constraint.

We also agree that the theorem also follows from the lower bound of
the variation of EQUALITY where $Y=[j]$. As we noted, there is not
much novelty in the proof as it is essentially the same as the proof
of set disjointness. We still keep the proof for completeness.


In response to the comments, we conjecture that the bipartiteness
problem has a super-logarithmic lower bound.
%
We also remarked that in all protocols presented in this paper, the
prover can construct the best-order proofs in polynomial time.
%
We also add the following questions asked by the reviewer as open
questions: 1) Do additional passes help? 2) Suppose that the edges
were presented as $\{u, v\}$ rather than $(u, v)$ -- would some
protocols now be impossible?

\paragraph{Reviewer 3:} We added some references mentioned by the
reviewer. We added a remark that the lower bounds in Theorem 4.2 and
5.3 are tight by showing simple algorithms for them. We also agree
that the lower bound in Theorem 5.3 is actually $\Omega(n \log n)$.
We now state this and also note that it is tight.

The reviewer asked:

\begin{quote}
Can one get a stronger result than Theorem 4.2 of an $\Omega(m)$
lower found for denser graphs? If not, can the authors explain why?
\end{quote}

We remarked that the algorithm that shows that this lower bound is
tight (after Theorem 4.2) also works for dense graphs. So, the
answer is no.
\end{document}
